package com.nowcoder.code.lcof;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class JZ35 {

    public static void main(String[] args) {


        ArrayList<RandomListNode> list = new ArrayList<>();
        RandomListNode head = new RandomListNode(0);
        list.add(head);
        for (int i = 1; i < 10; i++) {
            list.add(new RandomListNode(i));
            list.get(i - 1).next = list.get(i);
        }
        for (int i = 0; i < 10; i++) {
            list.get(i).random = list.get((i + 3) % 10);
        }


        System.out.println(new JZ35().Clone(head));

    }


    public RandomListNode Clone(RandomListNode pHead) {

        if (pHead == null) {
            return null;
        }

        RandomListNode rp = new RandomListNode(pHead.label);

        RandomListNode tmp = pHead;
        RandomListNode tmp1 = rp;

        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        map.put(tmp, tmp1);

        while (tmp.next != null) {
            tmp1.next = new RandomListNode(tmp.next.label);
            map.put(tmp.next, tmp1.next);
            tmp = tmp.next;
            tmp1 = tmp1.next;
        }

        tmp = pHead;
        tmp1 = rp;
        while (tmp != null) {
            tmp1.random = map.get(tmp.random);

            tmp = tmp.next;
            tmp1 = tmp1.next;
        }

        return rp;

    }


    public static class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

}

